package leetcode_2301_2400;

public class LeeCode_2370_faster {
    public static void main(String[] args) {
//        System.out.println(longestIdealString("acfgbd", 2));
//        System.out.println(longestIdealString("abcd", 3));
//        System.out.println(longestIdealString("pvjcci", 4));
        System.out.println(longestIdealString("eduktdb",15));
    }
    private static int longestIdealString(String s, int k) {
        int[] dp = new int[26];
        int n = s.length(), ans = 1;
        for(int i = n - 1; i >= 0; i--){
            char c = s.charAt(i);
            int start = (c - k) < 'a' ? 0 : c - k - 'a', end = (c + k) > 'z' ? 25 : c + k - 'a';
            int max = 0;
            for (int j = start; j <= end; j++) {
                max = Math.max(dp[j], max);
            }
            dp[c - 'a'] = 1 + max;
            ans = Math.max(dp[ c - 'a'], ans);
        }
        return ans;
    }
}
